package _17_剑指Offer;

// 需要注意，负数右移动，永远不可能到达0
public class _16_剑指Offer数值的整数次方 {

    public static void main(String[] args) {
        _16_剑指Offer数值的整数次方 v = new _16_剑指Offer数值的整数次方();
    }

    // 快速幂，求解
    public double myPow(double x, int n) {
        long num = n < 0? -(long)n: n;
        double ans = 1;
        // 移动num
        while (num != 0) {
            if ((num & 1) == 1) {
                ans *= x;
            }
            x *= x;
            num >>= 1;
        }
        return n < 0? 1 / ans: ans;
    }

    public double myPow2(double x, int n) {
        if (n == 0) return 1;
        if (n == -1) return 1 / x;
        int half = n >> 1;
        double halfValue = myPow2(x, half);
        return (n & 1) == 0? halfValue * halfValue: halfValue * halfValue * x;
    }

    public double myPow1(double x, int n) {
        return n < 0? 1 / pow(x, -(long) n): pow(x, -n);
    }

    public double pow(double x, long n) {
        if (n == 0) return 1;
        long half = n >> 1;
        double halfValue = pow(x, half);
        return (n & 1) == 0? halfValue * halfValue: halfValue * halfValue * x;
    }
}
